﻿
// Condition: Write a program that reads a rectangular matrix of size NxM and finds in it the square 3x3 that has
//            maximal sum of ots elements.

using System;



    class MaxSquare3x3
    {
        static void Main()
        {
            Console.Write("Enter number of rows (equal or bigger than 3) N=");
            int N = int.Parse(Console.ReadLine());
            Console.Write("Enter number of columns (equal or bigger than 3) M=");
            int M = int.Parse(Console.ReadLine());
            int[,] matrix = new int[N, M];
            int sum = 0;
            int maxSum = int.MinValue;
            int bestRow = -1;
            int bestCol = -1;



            // read from console elements of the matrix

            for (int row = 0; row < matrix.GetLength(0); row++)
            {
                for (int col = 0; col < matrix.GetLength(1); col++)
                {
                    Console.Write("Enter element[{0},{1}]:",row,col);
                    matrix[row, col] = int.Parse(Console.ReadLine());
                }
            }

            Console.WriteLine();
            Console.WriteLine("Original matrix is:");
            
            // print the matrix[n,m]

            for (int irow = 0; irow < N; irow++)
            {
                for (int icol = 0; icol < M; icol++)
                {
                    Console.Write(matrix[irow, icol] + " ");
                }
                Console.WriteLine();
            }
            Console.WriteLine();


            // with two loops we go through all possible sequence of submatrices 3x3 and count the sum
            // of elements

            for (int row = 0; row < N-2; row++)
            {
                for (int col = 0; col < M-2; col++)
                {
                    sum = matrix[row, col] + matrix[row, col + 1] + matrix[row, col + 2] +
                          matrix[row + 1, col] + matrix[row + 1, col + 1] + matrix[row + 1, col + 2] +
                          matrix[row + 2, col] + matrix[row + 2, col + 1] + matrix[row + 2, col + 2];
                    if (sum > maxSum)
                    {
                        maxSum = sum;
                        bestRow = row;
                        bestCol = col;
                    }
                }

            }


            // print maximal subsequence matrix

            Console.WriteLine("The sum of maximum subsequence is: {0}",maxSum);
            Console.WriteLine("The submatrix is:");

            for (int row = bestRow; row < bestRow+3; row++)
            {
                for (int col = bestCol; col < bestCol+3; col++)
                {
                    Console.Write(matrix[row,col]+" ");
                }
                Console.WriteLine();
            }
        }
    }

